1. Technical Field
The present invention relates to the technical field of graphic rendering and, in particular, to a method for detecting border tiles or border pixels of a primitive in a tile-based rendering system, for example in a sort-middle technique.
2. Description of the Related Art
A virtual three dimensional (3D) model (or simply “3D model”) is comprised of primitives in the form of polygons, such as triangles, which represent the skin of the 3D model. A graphic 3D engine draws polygons from the 3D model onto a two-dimensional (2D) surface, such as a screen.
A summary of the prior art rendering process can be found in: “Fundamentals of Three-Dimensional Computer Graphics”, by Watt, Chapter 5: The Rendering Process, pages 97 to 113, published by Addison-Wesley Publishing Company, Reading, Mass., 1989, reprinted 1991, ISBN 0-201-15442-0.
In a traditional pipeline, the primitives are processed in a submission order. A more efficient method is to break up the frame buffer into individual subsections (tiles) and to render them individually. Each tile includes one or more polygons or, more typically, a portion of one or more polygons.
A tile based rendering employs therefore a way to associate tiles covered by a primitive. A rasterizer renders all primitives of one tile, so which tile is covered by that primitive is found first.
To reduce the amount of tiles that each polygon is assigned to, a primitive or polygon binning method may be used. A polygon binning method excludes tiles that do not include any polygons or portions thereof prior to rasterization. The binning process also accomplishes some rasterization setup by identifying which polygons are contained by each tile.
A simple binning method provides for constructing a bounding box around the primitive. However, many tiles of the bounding box may still be outside the primitive.
According to another approach, the binning method calculates the equations of the lines formed by the edges of the primitive (in the standard y=mx+c format) and then tracks up the lines from vertex to vertex enabling the tiles which are transversed. This (depending on the size of the triangle) may leave some tiles in the middle. These can be checked and enabled by traveling along each row and enabling all tiles which are situated between two previously enabled tiles. This method requires to calculate reciprocal values and has therefore a very high cost.
According to an alternative method, the equations of the lines which form the sides of a polygon are not used and edge equations, which can be derived from a matrix formed by the vertex co-ordinates (“outcode method”), are employed. Therefore, each side of the triangle is associated with an edge equation. Any point on the line will satisfy this equation, with points on one side giving a positive evaluation and on the other a negative result. This property can be used to determine on which side of a line a point is, and therefore, by using three edge equations, whether a point is inside a triangle or not. In the present case, a tile is considered to be covered by a primitive if at least one of its corners is within the triangle. Therefore, this method requires checking against three edge equations for all the corners of the tiles. If all four corners of any tile are outside any of three edges, then that tile can be ignored.
According to another approach, called “midpoint method”, triangles are tiled by finding the midpoint of the edges and then disabling blocks of tiles that are outside these points. If a high accuracy is desired, also this method turns out to be quite cumbersome.
There is therefore the need of associating tiles to primitives in a more efficient way, in order to reduce the amount of processing to be performed by the 3D graphic engine.